/**
 * @ClassName Backpack
 * @Description TODO
 * @Author Quentin_zyj
 * @Date 2021/11/3 16:13
 */
public class Backpack {
    // 背包容量
    static int c;
    // 物品数
    static int n;
    // 物品数量数组
    static int[] w;
    // 物品价值数组
    static int[] p;
    // 当前重量
    static int cw;
    // 当前价值
    static int cp;
    // 当前最优价值
    static int bestp;

    static void back(int i) {
        if (i > n) {
            bestp = cp;
            return;
        }
        // 进入左子树
        if (cw + w[i] <= c) {
            cw += w[i];
            cp += p[i];
            back(i + 1);
            cw -= w[i];
            cw -= p[i];
        }
        if (bound(i + 1) > bestp) {
            back(i + 1);
        }
    }

    // 计算上界
    static int bound(int i) {
        // 剩余容量
        int cleft = c - cw;
        int b = cp;
        // 按照物品单位重量价值递减顺序装入物品
        while (i <= n && w[i] <= cleft) {
            cleft -= w[i];
            b += p[i];
            i++;
        }
        // 装满背包
        if (i <= n) {
            b += p[i] * cleft / w[i];
        }
        return b;
    }

}
